\section{Related Work} \label{sec:related}

Dense sugraphs often give key information about the network structure, its evolution and dynamics. To quote~\cite{GibsonKT05}:\emph{``Dense subgraph extraction is therefore a key primitive for any in-depth study of the nature of a large graph''}. Often, dense subgraphs may reveal information about community structure in otherwise sparse graphs e.g. the World Wide Web or social networks. They are good structures for studying the dynamics of a network and have been used, for example, to study link spam~\cite{GibsonKT05}.

The problem of finding size-bounded densest subgraphs has been studied extensively in the classical setting. Finding a maximum density subgraph in an undirected graph can be solved in polynomial time~\cite{G84,L}. However, the problem becomes NP-hard when a size restriction is enforced. In particular, finding a maximum density subgraph of size exactly $k$ is NP-hard~\cite{AHI,FKP} and no approximation scheme exists under a reasonable complexity assumption~\cite{K}. Recently Bhaskara et al.~\cite{BCVGZ12} showed integrality gaps for SDP relaxations of this problem.

Khuller and Saha~\cite{KS} considered the problem of finding densest subgraphs with size restrictions and showed that these are NP-hard. Khuller and Saha~\cite{KS} and also Andersen and Chellapilla~\cite{AC} gave constant factor approximation algorithms. Some of our algorithms are based on of those presented in~\cite{KS}.

In some recent work on computing dense subgraphs on large/online graphs, some noteworthy recent ones include~\cite{BahmaniKV12,AngelKSSST14}. Bahmani et al.~\cite{BahmaniKV12} consider computing dense subgraphs for static graphs in the streaming and distributed settings - the authors prove constant factor approximation guarantees with tight bounds on the streaming and distributed computational costs. Angel et al.~\cite{AngelKSSST14} consider graphs that have edge weight updates streaming by, and investigate algorithms that maintain dense subgraphs through these updates. This is perhaps the closest work we are aware of to our paper. They allow edges to have additive weight updates (say up to parameter $\delta$); the value of $\delta$ can be positive or negative. The authors prove algorithms and theoretical guarantees depending on this quantity and the streaming update model. 

In another line of work towards generally understanding how online graphs evolve, there has been studies that demonstrate how evolving graphs tend to densify over time~\cite{LeskovecKF07}. Such studies on understanding graph evolution processes such as preferential attachment, and resulting structural properties such as power-law degree distributions~\cite{faloutsos1999power,clauset2009power}, densification, diameter changes etc. is orthogonal yet interesting parallel to our context of actually computing and identifying dense structures~\cite{adamic2000power}. A recent survey on this topic is available at~\cite{aggarwal2014evolutionary}, and some structure and evolution properties focused on online social networks is due to Kumar et al.~\cite{kumar2010structure}.

In a recent work~\cite{SarmaLNT12}, dynamic graphs (with edges arriving over time) where considered for the density problem with the focus being on designing distributed algorithms in the congest model. Dynamic network topology and fault tolerance have always been core concerns of distributed computing~\cite{Attiya-WelchBook,lynch}. There are many models and a large volume of work in this area. A notable recent model is the dynamic graph model introduced by Kuhn, Lynch and Oshman in \cite{KuhnLO10}. They introduced a  stability property called $T$-interval connectivity (for $T\ge 1$) which stipulates the existence of a stable connected spanning subgraph for every $T$ rounds. 

Variants that go beyond studying densest subgraphs have also been considered. For e.g., in a very recent work, Tsourakakis~\cite{Tsourakakis14} look at the problem of finding near-cliques by considering triangle-dense graphs. See references therein for other such studies.

In addition, there have been several discussions on dynamic graphs in varying settings~\cite{Eppstein99dynamicgraph,Demetrescu:2010}. Several problems have been explored over the last decade or more~\cite{eppstein1997sparsification,walshaw1997parallel}, although relatively little is known for graph density computations. Different models for dynamic graphs were proposed as early as~\cite{harary1997dynamic}. Maintaining graph properties with evolving graphs over time was also considered in~\cite{feigenbaum2000dynamic}. One model considers allowing {\em lookahead} to handle dynamic changes~\cite{khanna1998certificates}. An example of a relatively more recent piece of work on dynamic graph clustering is~\cite{gorke2009dynamic}. We have only listed some of the representative papers here.

